#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>
#include <string.h>
#include <stdbool.h>

typedef struct 
{
    int *data; // --> 堆内存数组
    int size; // 总容量
    int top; // 栈顶元素位置
}seqStack;

seqStack *s1;
seqStack *s2;
seqStack *s3;

void show()
{
    int i, maxlen;

    int top1 = s1->top;
    int top2 = s2->top;
    int top3 = s3->top;

    maxlen = top1 > top2 ? top1 : top2;
    maxlen = (maxlen > top3 ? maxlen : top3) + 1;

    int a, b, c;
    a = b = c = maxlen;

    for(i=0; i<maxlen; i++)
    {
        if(top1 != -1 && a == top1+1)
            printf("%d", (s1->data)[top1--]);
        a--;
        printf("\t");
        
        if(top2 != -1 && b == top2+1)
            printf("%d", (s2->data)[top2--]);
        b--;
        printf("\t");
        
        if(top3 != -1 && c == top3+1)
            printf("%d", (s3->data)[top3--]);
        c--;
        printf("\n");
    }
    printf("s1\ts2\ts3\n-----------------\n\n");
}

seqStack *init_stack(int size)
{
    seqStack *s = calloc(1, sizeof(seqStack));
    if(s != NULL)
    {
        s->data = calloc(size, sizeof(int));
        if(s->data == NULL)
        {
            free(s);
            return NULL;
        }
        s->size = size;
        s->top = -1;
    }
    return s;
}

bool is_full(seqStack *s)
{
    return s->top == s->size-1;
}
bool is_empty(seqStack *s)
{
    return s->top == -1;
}


bool push(int data, seqStack *s)
{
    if(is_full(s))
        return false;

    s->data[++s->top] = data;
    return true;
}

bool pop(seqStack *s, int *px)
{
    if(is_empty(s))
	return false;

    *px = s->data[s->top--];
    return true;
}


// (n) s1 --> s2 (借助于s3)
void hanoi(int n, seqStack *s1, seqStack *s2, seqStack *s3)
{
   if(n == 0)
       return;

   hanoi(n-1, s1, s3, s2); // (n-1) s1 --> s3 (借助于s2)

   int x;
   pop(s1, &x);
   push(x, s2);

   hanoi(n-1, s3, s2, s1);// (n-1) s3 --> s2 (借助于s1)
}

int main(void)
{
    // 初始化三个空栈
    s1 = init_stack(10);
    s2 = init_stack(10);
    s3 = init_stack(10);

    push(3, s1);
    push(2, s1);
    push(1, s1);

    show();
    hanoi(3, s1, s2, s3);   
    show(); 
}


















